package com.zk.algorithm.tree;

import com.zk.algorithm.annotation.Easy;
import com.zk.algorithm.annotation.LeetCodeExplore;
import com.zk.algorithm.bean.TreeNode;

/**
 * 一棵树是否关于中心轴对称，树的镜像问题是这个 {@link InvertBinaryTree}
 *
 * @author zk
 */
@LeetCodeExplore
@Easy
public class SymmetricTree {

    // 一棵树是否关于中心轴对称
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }

        return isMirror(root.left, root.right);
    }

    private boolean isMirror(TreeNode left, TreeNode right) {
        //      1
        //    /   \
        // null  null
        if (left == null && right == null) {
            return true;
        }

        //      1
        //    /   \
        //  null   2
        if (left == null || right == null) {
            return false;
        }

        //       1
        //     /  \
        //   2     2 <= left   right
        //  / \   / \
        // 3  4  4   3
        return left.val == right.val &&
                // 左树的左 == 右树的右
                isMirror(left.left, right.right) &&
                // 左树的右 == 右树的左
                isMirror(left.right, right.left);
    }

}
